/*
leetcode 56 插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示
第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 
表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

 

示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 

提示：

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 10^5
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result;  // 用于存储结果
    int i = 0, n = intervals.size();
    
    // 1. 将所有在 newInterval 之前的区间加入结果
    // 遍历 intervals 的每个区间，如果当前区间的结束位置 (intervals[i][1]) 小于 newInterval 
    // 的起始位置 (newInterval[0])，说明当前区间完全位于 newInterval 的左侧。
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }
    
    // 2. 合并与 newInterval 重叠的区间
    //当前区间的起始位置 (intervals[i][0]) 小于等于 newInterval 的
    //结束位置 (newInterval[1])，说明它们存在重叠。
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    
    //将合并后的区间放到 result 中
    result.push_back(newInterval);
    
    // 3. 将剩余的区间加入结果
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }
    
    return result;
}

int main() {
    vector<vector<int>> intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
    vector<int> newInterval = {4, 8};
    vector<vector<int>> result = insert(intervals, newInterval);

    for (const auto& interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    return 0;
}

/*
示例推演：
输入：
intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
newInterval = {4, 8};

步骤 1：处理在 newInterval 之前的区间
遍历 intervals，直到遇到与 newInterval 重叠的区间为止。
区间 {1, 2} 在 newInterval 之前，直接加入 result：
result = {{1, 2}}

步骤 2：合并重叠区间
区间 {3, 5} 与 {4, 8} 重叠，合并后 newInterval 更新为 {3, 8}。
区间 {6, 7} 与 {3, 8} 重叠，合并后 newInterval 更新为 {3, 8}。
区间 {8, 10} 与 {3, 8} 重叠，合并后 newInterval 更新为 {3, 10}。
将合并后的区间 {3, 10} 加入 result：
result = {{1, 2}, {3, 10}}

步骤 3：处理剩余区间
剩余区间 {12, 16} 没有与 newInterval 重叠，直接加入 result：
result = {{1, 2}, {3, 10}, {12, 16}}

输出：
[[1, 2], [3, 10], [12, 16]]
*/